// FloodFill 算法：
// 借助深搜或者宽搜找性质相同的连通块

// 例题 7：
// 家居整理师将待整理衣橱划分为 m x n 的二维矩阵 grid，其中 grid[i][j] 代表一个需要整理的格子。
// 整理师自 grid[0][0] 开始 逐行逐列 地整理每个格子。
// 整理规则为：在整理过程中，可以选择 向右移动一格 或 向下移动一格，但不能移动到衣柜之外。
// 同时，不需要整理 digit(i) + digit(j) > cnt 的格子，其中 digit(x) 表示数字 x 的各数位之和。
// 请返回整理师 总共需要整理多少个格子。
//
//        示例 1：
//
//        输入：m = 4, n = 7, cnt = 5
//        输出：18
//
//
//        提示：
//
//        1 <= n, m <= 100
//        0 <= cnt <= 20

// 解题思路：
// 深搜找连通块

public class WardrobeFinishing {
    int r, c;
    int[] dx = {0, 1};
    int[] dy = {1, 0};
    boolean[][] check;
    int ret;
    public int wardrobeFinishing(int m, int n, int cnt) {
        r = m;
        c = n;
        check = new boolean[r][c];
        if(digit(0) + digit(0) <= cnt){
            dfs(0, 0, cnt);
        }
        return ret;
    }

    public void dfs(int i, int j, int cnt){
        ret++;
        check[i][j] = true;
        for(int k = 0; k < 2; k++){
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < r && y >= 0 && y < c && check[x][y] == false && digit(x) + digit(y) <= cnt){
                dfs(x, y, cnt);
            }
        }
    }
    public int digit(int num){
        int sum = 0;
        while(num > 0){
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}
